package leetcode.L416;

import java.util.Arrays;

class Solution1 {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;
        int target=sum/2;
        //看看能不能装满背包
        int[] dp=new int[target+1];
        for (int j = 1; j <= target; j++) {
            for (int i = 0; i <nums.length ; i++) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return  dp[target]==target;
    }
}